1. Field of the Invention
This invention relates generally to the field of elliptic curve cryptography, and more specifically, to elliptic curve point computation reliability.
2. Background
Cryptography systems based on elliptic curves are well known in the art. Elliptic curve cryptography (ECC) is widely used today as a method for encoding data to prevent unauthorized access to information that is stored or transmitted electronically. Increasingly, ECC systems are being used in data communications systems to ensure privacy, to authenticate transmissions, and to maintain data integrity.
Encryption in ECC systems involves finding a solution to the discrete logarithm problem from the group of points of an elliptic curve defined over a finite field. Using additive notation, this problem can be described as: given points P and Q in the group, find a number k such that kP=Q. Additional background on elliptic curves, and on mathematical operations performed on elliptic curves, is provided below.
Elliptic Curve Defined Over a Field
An elliptic curve Ep over a field Fp, where p is a prime greater than three, is composed by the set of points (x,y) that satisfy an elliptic curve equation such as y2≡x3+apx+bp mod p together with the point at infinity Op. The addition of points belonging to Ep that involves the point at infinity are the following: Op+Op=Op, P+Op=Op+P=P, P+(−P)=(−P)+P=Op. Equation (1) defines an expression for the point addition operation P1+P2 for which P1≠Op, P2≠Op, and P1+P2≠Op.λp≡(y2−y1)/(x2−x1)mod p for P1≠P2 or(3x12+ap)/(2y1)mod p for P1=P2 x3≡λp2−x1−x2 mod p y3≡λp(x1−x3)−y1 mod p  (1)
The points on Ep define a commutative group under the point addition operation defined above. The number of points in the curve is denoted here by #Ep. #Ep is also referred to as the order of the curve. The order of a point P is the scalar number np for which npP=Op. kP, where k is a scalar and P is a point on the curve, represents the addition of k points P (kP=P+P+ . . . +P). This operation, known as point multiplication, may be computed with iterated point additions.
Industry standards such as FIPS 186-2 (“Digital Signature Standard (DSS),” Federal Information Processing Standards Publication 186-2, U.S. Dept. of Commerce/NIST, January 2000), incorporated herein by reference, recommend the use of curves of prime orders in cryptography systems. In certain cases, subgroups of prime orders may also be used. For these curves and groups, the order of each point of interest with the exception of Op is the same. Using a group of prime order also guarantees that each point with the exception of Op is a generator of the group. Different multiples of a generator point define all the points in a group; for example, given that P is a generator, all the elements of the group correspond to the multiples iP where i=0 to np−1, where np represents the order of each point except Op.
Elliptic Curve Defined Over a Ring
An elliptic curve En over a ring Zn is composed by the set of points (x,y) that satisfy an elliptic curve equation such as y2≡x3+anx+bn mod n together with the point at infinity On.
The well-known Chinese Remainder Theorem (CRT) allows the representation of point P=(x,y)εEn as follows: P=[Pp, Pq]=[(xp, yp), (xq, yq)], where PpεEp, PqεEq, xp≡x mod p, xq≡x mod q, yp≡y mod p, and yq≡y mod q. Ep and Eq are elliptic curves defined over fields Fp and Fq. Op and Oq represent the points at infinity in Ep and Eq, and by convention On=[Op, Oq]. The constants in the curve expression for En are related to the constants on the expressions for the curves Ep and Eq in the following way: an=[ap, aq] and bn=[bp, bq], where ap≡an mod p, aq≡an mod q, bp≡bn mod p, and bq≡bn mod q. Throughout this disclosure, expressions inside brackets represent the projections modulo p and modulo q. The expression modulo n can be computed from the expressions modulo p and modulo q using Gauss's or Garner's algorithms. Descriptions of these algorithms are well known in the art, and can be found, e.g. in A. J. Menezes et al., “Handbook of Applied Cryptography,” CRC Press, 1997 (hereinafter “Menezes”), available at www.cacr.math.uwaterloo.ca/hac, and incorporated herein by reference.
The addition of points belonging to En can be defined so it is analogous to the addition of points belonging to curves defined over finite fields. The basic operations involving the point at infinity are the following: On+On=On, P+On=On+P=P, P+(−P)=(−P)+P=On. The addition P1+P2, where P1=[P1p, P1q] and P2=[P2p, P2q], can be computed according to Equation (2) given the following restrictions in addition to those shown in the equation: P1p≠Op. P1q≠Oq, P2p≠Op, P2q≠Oq, P1p+P2p≠Op in Ep, and P1q+P2q≠Oq in Eq.
The additional restrictions in Equation (2) establish consistent operations in Ep, Eq, and En. In this equation and throughout this disclosure, the symbol /≡ represents a non-congruent condition. A point addition where P1≠P2 corresponds to a point addition in Ep where P1p≠P2p and to a point addition in Eq where P1q≠P2q. The restrictions may not allow, for example, a point addition in En to correspond to a point addition in Ep (P1p≠P2p) and to a point double in Eq (P1q=P2q). The stated conditions guarantee the existence of the inverses (x2−x1)−1=[(x2p−x1p)−1, (x2q−x1q)−1] and (2y1)1=[(2y1p)−1, (2y1q)−1] and their computation either directly or using the CRT. Given the inverses relationships, one can verify the following relationships: λn=[λp, λq], x3=[x3p,x3q], and y3=[y3p,y3q].λn≡(y2−y1)(x2−x1)mod n for x1/≡x2 mod p and x1/≡x2 mod qor(3x12+an)/(2y1)mod n for x1≡x2 mod p and x1≡x2 mod qx3≡λn2−x1−x2 mod n y3≡λn(x1−x3)−y1 mod n  (2)
Equation (2) restricts the points in En that can be added. The following sections demonstrate how point addition and point multiplication operations can be performed using point addition in a ring in a way that avoids restricted point additions.
Point Multiplication
For large elliptic curves, point multiplications are computed with iterated point doubles and additions. Algorithm 1 (below) shows the double and add point multiplication algorithm, which is one of the simplest point multiplication algorithms. In Algorithm 1, step 2.1.1 uses a point double and step 2.1.2.1 uses a point addition.
For curves defined over finite fields, the expressions in Equation (1) can be used to compute these operations when Q≠O, P≠O, and P+Q≠O. For curves defined over rings, Algorithm 1 may be modified to comply with the restrictions described above for elliptic curves defined over a ring. Note that in general, a point multiplication is computed with iterated point additions and point doubles.
Point multiplication typically involves the computation of many point doubles and point additions (or point subtractions). When using affine coordinates in point double and point addition operations, inverse operations can be very costly in terms of processing time and memory usage. These inverse operations can be avoided by using projective coordinates. When using projective coordinates, the point double and the point addition operations require a larger number of multiplications and additions than when using affine coordinates but they do not require the computation of inverses. One inverse is required at the end of a point multiplication, when the resulting point is converted back to affine coordinates. Depending on the algorithm and the target performance, one or more additional inverses may be required to represent pre-computed points in affine coordinates.
Point multiplication when using projective coordinates typically involves the following steps: 1) conversion from affine coordinates, P=(x,y), to projective coordinates, P=(X,Y,Z); 2) computation of point multiplication Q=kP=k(X,Y,Z) using classical algorithms but with the point operations done in projective coordinates; and 3) conversion of the resulting point Q=(X,Y,Z) to affine coordinates Q=(x,y). Point multiplication algorithms are well known in the art and in industry standards. Additional examples can be found in G. Orlando, “Efficient Elliptic Curve Processor Architectures for Field Programmable Logic,” Ph.D. dissertation, ECE Dept., Worcester Polytechnic Institute, Worcester, Mass., March 2002, incorporated herein by reference.
Two projective coordinates representations, known as homogeneous coordinates and Jacobian coordinates, are described below. To highlight operations on curves defined over rings, the remainder of this disclosure defines curves and points operations in terms of n. These curves and operations are also applicable to embodiments that utilize curves defined over fields. In embodiments utilizing curves defined over fields, n is treated as a prime number.
Algorithm 1: Double and Add Point Multiplication Algorithm
      Inputs    ⁢          :            k    =                            ∑                      i            =            0                                m            -            1                          ⁢                              k            i                    ⁢                                    2              i                        ⁢                          /              *                        ⁢                          k              i                                          ∈                                                                  [                                  0                  ,                  1                                ]                            *                        /                                                  ⁢            P                    ⁢                      /            *                    ⁢          Point                ⁢                                  ⁢        on        ⁢                                  ⁢        the        ⁢                                  ⁢                              curve            ⁢                          .              *                                /                                          ⁢          Outputs                ⁢                  :                          Q    =    kP        Processing    ⁢          :                          1.        ⁢                  /          *                ⁢        Initialize            ⁢                          ⁢                        variables          ⁢                      .            *                          /                                  ⁢        1.1            ⁢      Q        =    O                      2.        ⁢                  /          *                ⁢        Compute            ⁢                          ⁢      the      ⁢                          ⁢      point      ⁢                          ⁢                        multiplication          ⁢                      .            *                          /                                  ⁢        2.1            ⁢                          ⁢      for      ⁢                          ⁢      i        =          m      -              1        ⁢                                  ⁢        down        ⁢                                  ⁢        to        ⁢                                  ⁢        0        ⁢                                  ⁢        do                        2.1      ⁢      .1      ⁢                          ⁢      Q        =                  2        ⁢                  Q          ⁢                      /            *                    ⁢          Point                ⁢                                  ⁢                              double            *                    /                                          ⁢          2.1                ⁢        .2        ⁢                                  ⁢        if        ⁢                                  ⁢                  k          i                    ≠              0        ⁢                                  ⁢        then                        2.1      ⁢      .2      ⁢      .1      ⁢      Q        =          Q      +                        P          ⁢                      /            *                    ⁢          Point                ⁢                                  ⁢                                            addition              *                        /                                                  ⁢            3.                    ⁢                      /            *                    ⁢          Return                ⁢                                  ⁢                              result            ⁢                          .              *                                /                                          ⁢          3.1                ⁢                                  ⁢                  Return          ⁡                      (            Q            )                              Homogeneous Coordinates
Homogeneous coordinates represent points with three coordinates (X, Y, Z). Points represented in this form satisfy the homogeneous form of the elliptic curve equation shown in Equation (3).Y2Z≡X3+aXZ2+bZ3 mod n  (3)
The conversion from affine to homogeneous coordinates is trivial. Assuming that P=(x, y), the representation of P in homogeneous coordinates is P=(X=x, Y=y, Z=1). The conversion of P=(X, Y, Z) from homogeneous to affine coordinates is P=(X/Z, Y/Z) provided that the divisions X/Z mod n and Y/Z mod n exist. By convention the point O in homogeneous coordinates is represented by O=(0, Y, 0).
Equation (4) shows expressions for point double, (X3, Y3, Z3)=2(X1, Y1, Z1), and Equation (5) shows expressions for point addition, (X3, Y3, Z3)=(X1, Y1, Z1)+(X2, Y2, Z2).(X3,Y3,Z3)=2(X1,Y1,Z1)w≡3X12+aZ12 mod n X3≡2Y1Z1(w2−8X1Y12Z1)mod n Y3≡4Y12Z1(3wX1−2Y12Z1)−w3 mod n Z3≡8Y13Z13 mod n  (4)(X3,Y3,Z3)=(X1,Y1,Z1)+(X2,Y2,Z2)u≡Y2Z1−Y1Z2 mod n v≡X2Z1−X1Z2 mod n X3≡v{Z2(u2Z1−2v2X1)−v3} mod n Y3≡Z2(3uv2X1−v3Y1−u3Z1)+uv3 mod n Z3′≡v3Z1Z2 mod n  (5)
Equations (4) and (5) have the property that the addition of P and −P result in the conventional representation for O: (X3, Y3, Z3)=(X1, Y1, Z1)+(X2, Y2, Z2)=(0, (−2Y1Z2)3Z1Z2, 0) when X1/Z1≡X2/Z2 mod n and Y1/Z1≡−Y2/Z2 mod n; and (X3, Y3, Z3)=2(X1, Y1, Z1)=(0,−(3X12+aZ12)3, 0) when Y1/Z1≡0 mod n (i.e., P1 is a point of order two). When adding a point of the form O=(0, Y, 0), the expressions in Equation (4) and Equation (5) yield O=(0, 0, 0), which corresponds to O=(0, Y, 0) with Y=0.
The point double expressions yield valid results for 2P=P+(−P)=O and 2O=O. The point addition expressions yield valid result for P+(−P)=O but they yield invalid results for P+O=P when P≠O; for which, the expressions in Equation (5) compute P+O=O. The last case is handled explicitly by the point addition operation, which compares the values of the input points against O and depending on the results computes the following: R=P+Q if P≠O, Q≠O, and P≠Q using Equation (5); sets R=P if Q=O; or sets R=Q if P=O. In addition, the point addition operation performs a point double operation using Equation (4) if P=Q.
According to known complexity estimates, a point double operation requires 11 modular multiplications and a point addition requires 12 modular multiplications. These complexity estimates ignore additions because their complexities are usually much lower than the complexities of multiplications.
Jacobian Coordinates
Jacobian coordinates represent points with three coordinates (X, Y, Z). Points represented in this form satisfy the projective form of the elliptic curve equation shown in Equation (6).Y2≡X3+aXZ4+bZ6 mod n  (6)
The conversion from affine to Jacobian coordinates is trivial. Assuming that P=(x, y), the representation of P in Jacobian coordinates is P=(X=x, Y=y, Z=1). The conversion of P=(X, Y, Z) from Jacobian to affine representation is P=(X/Z2, Y/Z3) provided that the divisions X/Z2 mod n and Y/Z3 mod n exist. By convention the point O in Jacobian coordinates is represented by O=(t2, t3, 0).
For Jacobian coordinates, Equation (7) shows the expressions for point double, (X2, Y2, Z2)=2(X1, Y1, Z1), and Equation (8) shows the expressions for point addition, (X2, Y2, Z2)=(X0, Y0, Z0)+(X1, Y1, Z1).(X2,Y2,Z2)=2(X1,Y1,Z1)M≡(3X12+aZ14)mod n Z2≡2Y1Z1 mod nS≡4X1Y12 mod nX2≡M2−2S mod n T≡8Y14 mod nY2≡M(S−X2)−T mod  (7)(X2,Y2,Z2)=(X0,Y0,Z0)+(X1,Y1,Z1)U0≡X0Z12 mod nS0≡Y0Z13 mod nU1≡X1Z02 mod nS1≡Y1Z03 mod nW≡U0−U1 mod n R≡S0−S1 mod n T≡U0+U1 mod n M≡S0+S1 mod n Z2≡Z0Z1W mod nX2≡R2−TW2 mod n V≡TW2−2X2 mod n Y2≡(VR−MW3)/2 mod n  (8)
Equations (7) and (8) have the property that the addition of P and −P result in the conventional representation for O: (X2, Y2, Z2)=(X0, Y0, Z0)+(X1, Y1, Z1)=(t2, t3, 0) where t=−2Y1Z03 when X0/Z02≡X1/Z12 mod n and Y0/Z03≡−Y1/Z13 mod n; and (X2, Y2, Z2)=2(X1, Y1, Z1)=(t2, t3, 0) where t=−(3X12+aZ14) when Y1/Z13≡0 mod n (i.e., P1 is a point of order two).
When adding a point of the form O=(u2, u3, 0), the expressions in Equation (7) yield 2O=(t2, t3, 0), which matches the expected result. When adding a point of the form O=(u2, u3, 0), the expressions in Equation (8) yield P+O=O=(0,0,0), which corresponds to O=(t2, t3, 0) with t=0, instead of the expected result P+O=P when P≠O. The last case is handled explicitly by the point addition operation, which compares the values of the input points against O and depending on the results computes the following: R=P+Q if P≠O, Q≠O, and P≠−Q using Equation (8); sets R=P if Q=O; or sets R=Q if P=O. In addition, the point addition operation performs a point double operation using Equation (7) if P=Q.
When using Jacobian coordinates, a point double operation requires 10 modular multiplications if a/≡−3 mod n and 8 modular multiplications if a≡−3 mod n. Point addition requires 16 field multiplications when Z1/≡1 mod n and 11 field multiplications when Z1≡1 mod n. Some standards, such as FIPS 186-2, suggest the use of curves for which a≡−3 mod n.
Point double is the most common operation in point multiplication. As a consequence, Jacobian coordinates lead to faster point multiplications than homogeneous coordinates for curves for which a≡−3 mod n and for point multiplications that yield both the x and y coordinates of the resulting points. Some algorithms, usually specified in terms of homogenous coordinates, do not use the y coordinates of the resulting points or can recover them. Examples of these algorithms can be found in N. Demytko, “A New Elliptic Curve Based Analogue of RSA,” Advances in Cryptology—Eurocrypt '93 (LNCS 765), pp. 40-49, Springer-Verlag, 1994 (hereinafter “Demytko”), and also in E. Brier et al., “Weierstrass Elliptic Curves and Side-Channel Attacks,” Public Key Cryptography (LNCS 2274), pp. 335-345, Springer-Verlag, 2002, both of which are incorporated by reference herein.
Verification of Decryption Computations
The elliptic curve point additions and point multiplications described above are the basic mathematical operations used in elliptic curve cryptography. These operations are routinely applied, for example, in computerized cryptography systems when implementing key agreement protocols for secure communications. During implementation, erroneous computations can sometimes arise as a result of random errors, or as a result of errors maliciously induced by an attacker or active adversary. Thus, for security purposes, it is often desirable to perform independent verification of a computation in order to increase system reliability.
In a conventional system, reliable computation can be achieved with two redundant engines that independently perform the same computation or with a single engine that performs the same computation twice. If the results from the two operations match, the common result is assumed to be correct, and the communication is deemed reliable and secure. The main problem with these approaches is that they double the complexity of an already complex, time-consuming, and memory-intensive operation.